package chapter2;

import util.PrintUtils;

/**
 * 堆排序
 */
public class HeapSort {

    public void buildMaxHeap(int[] arr) {
        if (arr == null || arr.length <= 1)  return;

        /**
         * 构造最大堆
         * (arr.length / 2 - 1) 堆最右的第一个非子节点
         */
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            int l = i * 2 + 1;
            int r = i * 2 + 2;

            // 比较左子节点和右子节点，选中大的那一个
            int m = r == arr.length ? l : arr[l] > arr[r] ? l : r;

            if (arr[i] < arr[m]) {
                int t = arr[i];
                arr[i] = arr[m];
                arr[m] = t;

                for (int j = m; j <= arr.length / 2 - 1; ) {
                    int l1 = j * 2 + 1;
                    int r1 = j * 2 + 2;

                    // 比较左子节点和右子节点，选中大的那一个
                    int m1 = r1 == arr.length ? l1 : arr[l1] > arr[r1] ? l1 : r1;

                    if (arr[m1] > arr[j] ) {
                        int z1 = arr[m1];
                        arr[m1] = arr[j];
                        arr[j] = z1;
                        j = m1;
                    } else {
                        break;
                    }
                }
            }

        }

        // 顶点置底，并把数组中最后一个元素置顶，再执行下沉操作
        for (int b = arr.length - 1; b >= 0; b--) {
            int t = arr[0];
            arr[0] = arr[b];
            arr[b] = t;

            for (int i = 0; i <= b / 2 - 1; ) {
                int l = 2 * i + 1;
                int r = 2 * i + 2;

                int m = r == b ? l : arr[l] > arr[r] ? l : r;

                if (arr[m] > arr[i]) {
                    int z = arr[m];
                    arr[m] = arr[i];
                    arr[i] = z;
                    i = m;
                } else {
                    break;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {2,1,8,5,9,4,3,0,7,6};
        HeapSort sort = new HeapSort();
        sort.buildMaxHeap(arr);
        PrintUtils.PrintArray(arr);
    }

}
